package sort.leetcode.easy;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author bruin_du
 * @description 最小的k个数
 * @date 2022/5/31 10:17
 **/
public class Offer40_GetLeastNumbers {
    ThreadLocalRandom random = ThreadLocalRandom.current();
    public int[] getLeastNumbers(int[] arr, int k) {
        method(arr,0,arr.length - 1,k - 1);
        return Arrays.copyOf(arr,k);
    }

    private void method(int[] arr, int left, int right,int k) {
        if(left >= right) return;
        int mid = partition(arr,left,right);
        if(mid > k){
            method(arr,left,mid - 1,k);
        }else if(mid < k){
            method(arr, mid + 1, right, k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int mid = random.nextInt(left,right);
        swap(arr,left,mid);
        int v = arr[left];
        int i = left,j = left + 1;
        while(j <= right){
            if(arr[j] < v){
                swap(arr,++i,j);
            }
            j++;
        }
        swap(arr,left,i);
        return i;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
